package stack;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 20.有效括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * 1. 左括号必须用相同类型的右括号闭合。
 * 2. 左括号必须以正确的顺序闭合。
 * 3. 每个右括号都有一个对应的相同类型的左括号。
 */
public class isValid {
    /**
     * 一刷
     */
    public boolean isValid(String s) {

        if (s == null || s.length() == 0)
            return true;
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (c == ')' || c == '}' || c == ']') {
                if (stack.isEmpty())
                    return false;
                Character temp = stack.pop();
                if (c == ')' && temp != '(') {
                    return false;
                } else if (c == '}' && temp != '{') {
                    return false;
                } else if (c == ']' && temp != '[') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    /**
     * 二刷
     */
    public boolean isValid2(String s) {

        Stack<Character> stack = new Stack<>();
        char[] array = s.toCharArray();
        if (array.length % 2 != 0)
            return false;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == '(' || array[i] == '{' || array[i] == '[') {
                stack.push(array[i]);
            } else if (stack.empty())
                return false;
            else if (array[i] == ')') {
                if ('(' != stack.pop()) {
                    return false;
                }
            } else if (array[i] == '}') {
                if ('{' != stack.pop()) {
                    return false;
                }
            } else if (array[i] == ']') {
                if ('[' != stack.pop()) {
                    return false;
                }
            }
        }
        if (stack.empty())
            return true;
        return false;
    }

    /**
     * hot100一刷
     * hot100二刷
     */
    public boolean isValid3(String s) {
        if (s.length() % 2 == 1)
            return false;
        Deque<Character> q = new LinkedList<>();
        char[] arry = s.toCharArray();
        for (int i = 0; i < arry.length; i++) {
            if (arry[i] == '{') {
                q.push('}');
            } else if (arry[i] == '[') {
                q.push(']');
            } else if (arry[i] == '(') {
                q.push(')');
            } else {
                if (q.isEmpty()) return false;
                if (q.pop() != arry[i]) return false;
            }
        }
        return q.size() == 0;
    }

    public static boolean isValid222(String s) {
        Deque<Character> q = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                q.push(')');
            } else if (c == '[') {
                q.push(']');
            } else if (c == '{') {
                q.push('}');
            } else {
                if (q.isEmpty() || q.pop() != c)
                    return false;
            }
        }
        return q.isEmpty();
    }

}
